home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericKeylessHeap.h,v < prev    next >
Text File  |  1988-10-12  |  3KB  |  166 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @ * @;
  6.  
  7.  
  8. 1.1
  9. date     88.09.18.16.42.06;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @//
  25. // Define the following things:
  26. //    HEAP_NAME    -- the name of the heap type
  27. //    HEAP_INDEX    -- the index type; defaults to unsigned short
  28. //    HEAP_INDEX_NULL    -- the null value for the heap index; defaults to 65535
  29. //    HEAP_BASE_CLASS    -- the base class for the new heap
  30. //
  31. // Furthermore, the item type should be a type with the name
  32. //    GENERIC2(HEAP_NAME,Item)
  33. //
  34. // This type can be anything (simple, class, typedef) that provides
  35. // comparison operatiohns.
  36. //
  37.  
  38. #include "Awesime.h"
  39. #include "Generic.h"
  40.  
  41. #ifndef HEAP_INDEX
  42. #define HEAP_INDEX unsigned short
  43. #endif
  44.  
  45. #ifndef HEAP_INDEX_NULL
  46. #define HEAP_INDEX_NULL 0xffff
  47. #endif
  48.  
  49. #ifndef HEAP_BASE_CLASS
  50. #define HEAP_BASE_CLASS public Awesime
  51. #endif
  52.  
  53. //
  54. //    The following are simplifications of the preceeding names;
  55. //    they make the following code much more readable
  56. //
  57. //    However, for safety, they are undef'd at the end of the .h file,
  58. //    so you'll need to re-def them in your .cc file if you want to use them.
  59. //
  60.  
  61. #define NIL    GENERIC2(HEAP_NAME,Null)
  62. #define INDEX    GENERIC2(HEAP_NAME,Index)
  63. #define ITEM    GENERIC2(HEAP_NAME,Item)
  64.  
  65. typedef HEAP_INDEX INDEX;
  66.  
  67. extern const INDEX NIL;
  68.  
  69. typedef struct {
  70.     ITEM item;
  71.     INDEX sibling;
  72.     INDEX children;
  73. } GENERIC2(HEAP_NAME,Record);
  74.  
  75. class HEAP_NAME : HEAP_BASE_CLASS {
  76.  
  77.     GENERIC2(HEAP_NAME,Record) *storage;
  78.     char *pValid;
  79.     int elements;
  80.     INDEX allocatedSize;
  81.     INDEX freelist;
  82.     INDEX root;
  83.  
  84.     void makeRoom(int atLeast);
  85.  
  86.     INDEX makeChild(INDEX a, INDEX b);
  87.  
  88.     inline INDEX getCell() {
  89.     if (freelist == GENERIC2(HEAP_NAME,Null)) {
  90.         makeRoom(0);
  91.     }
  92.     INDEX cell = freelist;
  93.     pValid[freelist] = 1;
  94.     freelist = storage[freelist].sibling;
  95.     elements++;
  96.     return(cell);
  97.     }
  98.  
  99.     inline void returnCell(INDEX cell) {
  100.     storage[cell].sibling = freelist;
  101.     pValid[cell] = 0;
  102.     freelist = cell;
  103.     elements--;
  104.     }
  105.  
  106. public:
  107.     HEAP_NAME(int length = 0, bool xdebug = 0);
  108.  
  109.     void add(ITEM &item);
  110.     bool remove(ITEM &removed);
  111.     
  112.     //
  113.     //    The next four members allow you to search a HEAP_NAME and mark
  114.     //    items as invalid. 
  115.     //
  116.     //    doStart initilizes the index and returns the first item in the list.
  117.     //    doNext moves to the next item and returns that item.
  118.     //    Both return a bool indicating whether the value in item has any
  119.     //    meaning. When bool=FALSE, you've searched everything.
  120.     //  Call doDone at the end to insure compatibility with subclasses.
  121.     //
  122.  
  123.     virtual bool doStart( INDEX &index);
  124.     virtual bool doDelete(INDEX &index);
  125.     virtual bool doNext( INDEX &index);
  126.     virtual void doDone();
  127.  
  128.     inline INDEX minItem() {
  129.     return(root);
  130.     };
  131.  
  132.     inline bool valid(INDEX index) {
  133.     return ( pValid[index] );
  134.     }
  135.  
  136.     inline ITEM & item(INDEX i) {
  137.     return( storage[i].item );
  138.     }
  139.  
  140.     inline INDEX maxIndex() {
  141.     return(allocatedSize);
  142.     }
  143.  
  144.     inline bool isEmpty() {
  145.     return(elements <= 0);
  146.     }
  147.  
  148.     inline unsigned int size() {
  149.     return(elements);
  150.     }
  151.  
  152.     virtual void classPrintOn(ostream& s);
  153. };
  154.  
  155. #undef INDEX
  156. #undef ITEM
  157. #undef NIL
  158.  
  159. #undef HEAP_NAME
  160. #undef HEAP_ITEM
  161. #undef HEAP_INDEX
  162. #undef HEAP_INDEX_NULL
  163. #undef HEAP_BASE_CLASS
  164.  
  165. @
  166.